package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _662_widthOfBinaryTree {
    //前序遍历
    private class Node{
        TreeNode node;
        int level;

        Node(TreeNode node, int level){
            this.node = node;
            this.level = level;
        }
    }
    //BFS
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){return 0;}
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(root, 1));
        int maxSize = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            int startSeqNo = 0, endSeqNo = 0;
            for(int i=0 ; i<size; i++){

                Node curr = queue.poll();
                TreeNode node = curr.node;
                int seqNo = curr.level;
                if (i==0){startSeqNo = seqNo;}
                if(i==size-1){endSeqNo=seqNo;}
                if(node.left!=null){queue.add(new Node(node.left, 2*seqNo));}
                if(node.right!=null){queue.add(new Node(node.right, 2*seqNo+1));}
            }
            maxSize = Math.max(endSeqNo-startSeqNo+1, maxSize);
        }
        return maxSize;
    }

    //DFS
    public int widthOfBinaryTree1(TreeNode root) {
        return dfs(root, 0, 1, new ArrayList<>(), new ArrayList<>());
    }
    private int dfs(TreeNode node, int level, int seqNo, List<Integer> start, List<Integer> end) {
        if (node == null) {return 0;}

        // 前序 - 递
        if (start.size() == level) { //level 层的第一个节点
            start.add(seqNo);
            end.add(seqNo);
        } else {
            end.set(level, seqNo);
        }

        int leftMaxWidth = dfs(node.left, level + 1, 2 * seqNo, start, end);
        int rightMaxWidth = dfs(node.right, level + 1, 2 * seqNo + 1, start, end);

        // 后序，回溯 - 归
        int currWidth = end.get(level) - start.get(level) + 1;
        return Math.max(currWidth, Math.max(leftMaxWidth, rightMaxWidth));
    }
}
